package leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class Code015_MinSubArrayLen {


    // 这里没必要使用双端队列搞滑动窗口，时间复杂度，空间复杂度都上去了
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0;
        Integer minSubArraySize = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // 头过期
            while (sum >= target) {
                minSubArraySize = Math.min(deque.size(), minSubArraySize);
                int first = deque.pollFirst();
                sum -= nums[first];
            }

            deque.offerLast(i);
            sum += nums[i];
        }

        while (sum >= target && deque.size() > 1) {
            minSubArraySize = Math.min(deque.size(), minSubArraySize);
            int first = deque.pollFirst();
            sum -= nums[first];
            if (deque.size() == 1 && nums[deque.peekFirst()] >= target) {
                return 1;
            }
        }
        return sum == 0 || minSubArraySize == Integer.MAX_VALUE ? 0 : minSubArraySize;
    }

    // 这里没必要使用双端队列搞滑动窗口，时间复杂度，空间复杂度都上去了
    public static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int sum = 0;
        Integer minSubArraySize = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            deque.offerLast(i);
            sum += nums[i];
            // 头过期
            while (!deque.isEmpty() && sum >= target) {

                minSubArraySize = Math.min(deque.size(), minSubArraySize);
                int first = deque.pollFirst();
                sum -= nums[first];

            }

        }
        return minSubArraySize == Integer.MAX_VALUE ? 0 : minSubArraySize;
    }


    public static int minSubArrayLen3(int target, int[] nums){
        int res = Integer.MAX_VALUE;
        int left = 0;
        int total = 0;
        for(int right = 0; right < nums.length;right++){
            total += nums[right];
            while(total >= target){
                res = Math.min(res, right - left + 1);
                total -= nums[left++];
            }
        }
        return res > nums.length ? 0 : res;
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println(minSubArrayLen2(11, nums));
    }
}
